package xu.dp.solution;

public class Solution1027 {
    /*
     * 最长等差数列
     * 使用动态规划思想来求解这道题目，这里以数组 [2,4,6,9,4] 为例来进行讲解，首先创建一个和数组相同大小
     * 的 dp 数组，不过每一个 dp 数组中的元素都为字典 map，具体如下：
     * dp[0]: 空
     * dp[1]: <2,2>
     * dp[2]: <4,2> <2,3>
     * dp[3]: <7,2> <5,2> <3,2>
     * dp[4]: <2,2> <0,2> <-2,2> <-5,2>
     * 遍历到 dp[i] 元素时，依次遍历 dp[k] (0 <= k < i) 元素，如果 interval = dp[i] - dp[k]，那么检查
     * dp[k] 元素的字典中是否存在和 interval 对应的数据 len，如果存在就说明 dp[k] 也和之前的数组数字形成了等差
     * 数列。那么就将 <interval, len + 1> 保存到 dp[i] 的字典中
     */
}
